package pers.qianyu.month_202011.date_20201112;

import java.util.*;

/**
 * 51. N 皇后
 * https://leetcode-cn.com/problems/n-queens/
 *
 * @author mizzle rain
 * @date 2020-11-12 20:31
 */
public class NQueens {
    private List<List<String>> result = new ArrayList<>();
    private List<Integer> pre = new ArrayList<>();
    private int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        char[][] cb = new char[n][n];
        for (int i = 0; i < cb.length; i++) {
            Arrays.fill(cb[i], '.');
        }
        recur(cb);
        return result;
    }

    private void recur(char[][] cb) {
        int size = pre.size();
        if (size == n) {
            List<String> list = arrayToList(cb);
            result.add(list);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid(i)) {
                continue;
            }
            cb[size][i] = 'Q';
            pre.add(i);
            recur(cb);
            pre.remove(Integer.valueOf(i));
            cb[size][i] = '.';
        }
    }

    private boolean isValid(int cur) {
        if (pre.contains(cur)) {
            return true;
        }
        int size = pre.size();
        if (size == 0) {
            return false;
        }
        for (int index = 0; index < size; index++) {
            Integer item = pre.get(index);
            // (index, item) 和点 (size,cur) 的斜率 = 1 / -1
            if ((item - cur == index - size) || (item - cur == -index + size)) {
                return true;
            }
        }
        Integer last = pre.get(size - 1);
        if (cur == last - 1 || cur == last + 1) {
            return true;
        }
        return false;
    }

    private List<String> arrayToList(char[][] cb) {
        List<String> list = new ArrayList<>();
        for (char[] c : cb) {
            StringBuilder sb = new StringBuilder();
            for (char c1 : c) {
                sb.append(c1);
            }
            list.add(sb.toString());
        }
        return list;
    }

    private void printArr(char[][] cb) {
        System.out.println("============================");
        for (int i = 0; i < cb.length; i++) {
            for (int k = 0; k < cb[i].length; k++) {
                System.out.print(cb[i][k] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        List<List<String>> lists = nQueens.solveNQueens(5);
        // 判断是否有重复
        System.out.println(lists.size());
        System.out.println(lists.stream().distinct().count());
        // 打印结果
        for (List<String> list : lists) {
            System.out.println("-----------------------------");
            for (String s : list) {
                char[] arr = s.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    System.out.print(arr[i] + " ");
                }
                System.out.println();
            }
        }
    }
}
